אני רוצה לדעת האם יש שימוש ברקורסיה בטוב ואם כן באיזה מצבים?
מבחינת יעילות וזמן ריצה מי יותר מהירה רקורסיה או לולאה?
ואם יש מקומות שהיא עדיפה איך להבין אותה?

1 תשובות

avatar ענה intval ב 12 לדצמבר 2013 #

בהגדרה הכי פשוטה, פונקציה רקורסיבית היא פונקציה שמעפילה את עצמה.
ברוב המקרים רקורסיה אפשר להחליף בלולאה ובהרבה שפות מקומפלות הקומפיילר לפעמים בכוונה הופך רקורביות ללולאות אם אפשר.

מצד שני, יש מקרים שבהם לא תמיד אפשר לבצע לולאה. המקרים האלה בדרך כלל הם כשאתה עובד עם מבנה נתונים מורכב ועמוק, כמו עץ; באיחוד כשאתה לא יודע מה העומק. בתור דוגמה ממש פשוטה, נניח שיש לך מערך רב-מימדי, מערך שמכיל מערכים, שמכילים מערכים, שמכילים מערכים שמכילים מספרים. אם אתה לא יודע מה עומק וגודל המערכים מראש - אין לך שום אפשרות לכתוב את כמות הלולאות הנכונה מראש. אותו דבר נכון גם למבני נתונים אחרים שיש להם עומק.

דוגמה קצת פחות ישרה היא למשל מערכת mvc. נניח שיש לך פונקציה בשם Render. היא לוקחת תבנית html כלשהי ומציגה אותה. תבנית html אחת יכולה להכיל בתוכה תת תבניות ותת תבניות. בגלל שלתבנית הזאת יש עומק שאתה לא יכול לצפות מראש - תצטרך להשתמש ברקוריסה. הנה דוגמה לרקורסיה. שים לב שבסופו של דבר הפונקציה Render בתוכה שוב ושוב מפעילה את הפונקציה Render.

אותו דבר קורה בדפדפן כשהוא מנסה לצייר עמוד על המסך. אם בעמוד יש iframe, הוא יצטרך להפעיל את פונקציית ציור המסך ובאמצע הקריאה הראשונה להפעיל קריאה נוספת עבור אותו האייפריים. זה יקרה שוב אם בתוך אותו האייפריים יש עוד איפרייים וכו'.

מה שמשתוף לכל המקרים האלה הוא שמדובר במבנה נתונים עם עומק שאתה לא יודע מראש.

מעבר לזה, רקורסיה היא עוד טכניקה בארגז הכלים של המתכנת. היא מאפשרת לכתוב אלגוריטמים שלא נוח לעשות עם לולאות. בתור דוגמה פשוטה - merge sort. גם זה לא כל כך אקטואלי למתכנתי PHP בגלל שאין להם כל כך סיבה להתעסק באלגוריטמים.